"""
难度：中等
实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。不得使用库函数，同时不需要考虑大数问题。
示例 1：
输入：x = 2.00000, n = 10
输出：1024.00000
示例 2：
输入：x = 2.10000, n = 3
输出：9.26100
示例 3：
输入：x = 2.00000, n = -2
输出：0.25000
解释：2-2 = 1/22 = 1/4 = 0.25
"""
"""
常规方法是直接将 x 累乘 n 次得出结果，时间复杂度为 。可以利用快速幂来减少时间复杂度。
如果 n 为偶数，。如果 n 为奇数，。
 又可以继续向下递归划分。则我们可以利用低纬度的幂计算结果，来得到高纬度的幂计算结果。
这样递归求解，时间复杂度为 ，并且递归也可以转为递推来做。
需要注意如果 n 为负数，可以转换为 
"""


class Solution:
    def myPow(self, x: float, n: int) -> float:
        if x == 0.0:
            return 0.0
        res = 1
        if n < 0:
            x = 1 / x
            n = -n
        while n:
            if n & 1:
                res *= x
            x *= x
            n >>= 1
        return res
